package com.github.yangyishe.p200;

import com.github.yangyishe.TreeNode;

/**
 * 124. 二叉树中的最大路径和
 * https://leetcode.cn/problems/binary-tree-maximum-path-sum/?envType=study-plan-v2&envId=top-interview-150
 *
 * 二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
 *
 * 路径和 是路径中各节点值的总和。
 *
 * 给你一个二叉树的根节点 root ，返回其 最大路径和 。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [1,2,3]
 * 输出：6
 * 解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6
 * 示例 2：
 *
 *
 * 输入：root = [-10,9,20,null,null,15,7]
 * 输出：42
 * 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
 *
 *
 * 提示：
 *
 * 树中节点数目范围是 [1, 3 * 104]
 * -1000 <= Node.val <= 1000
 */
public class Problem124 {
    public static void main(String[] args) {
        Integer[] root=new Integer[]{9,6,-3,null,null,-6,2,null,null,2,null,-6,-6,-6};
        TreeNode instance = TreeNode.getInstanceNew(root);

        Problem124 problem124 = new Problem124();
        int i = problem124.maxPathSum(instance);
        System.out.println(i);

    }

    /**
     * 思路:
     * 从小的子树开始, 到树的规模逐渐变大. 每个树实际上有两个最大值.
     * a. 一个端点在顶点的最大值
     * b. 允许端点不再顶点的最大值.
     * 其中, b通常可能比a要大, 但也可能相等. b>=a
     *
     * 将两颗相邻的子树合并为一个更大的子树, 求最大路径和时, 同样维护这两个值:
     * a. 端点在顶点的最大值, 等于topVal+Max(leftA,rightA,0)
     * b. 为Max(topVal+Max(leftA,0)+Max(rightA,0),leftB,rightB) leftA和leftB, 没有就不参与
     *
     * 确定以上规则后, 接下来就是遍历递归+带值判断了, 还是用前序遍历法
     * 相当于:
     * a=topVal+max(leftA,leftB,0)
     * b=max(topVal+Max(leftA,0)+Max(rightA,0),max)
     *
     * 官方题解:
     * 使用了全局变量, 简化了逻辑, 更加优雅.
     * 即, 将实际的b挂在了全局变量中, 而仅将需要回溯的a作为参数返回.
     *
     *
     * @param root
     * @return
     */
    public int maxPathSum(TreeNode root) {
        int[] max = findMax(root);
        return max[1];
    }

    public int[] findMax(TreeNode node){
        if(node.left==null&&node.right==null){
            return new int[]{node.val,node.val};
        }

        int[] leftMax=new int[2];
        if(node.left!=null){
            leftMax=findMax(node.left);
        }

        int[] rightMax=new int[2];
        if(node.right!=null){
            rightMax=findMax(node.right);
        }

        int maxA=node.val+Math.max(Math.max(leftMax[0],rightMax[0]),0);

        int maxB=node.val+Math.max(leftMax[0],0)+Math.max(rightMax[0],0);
        if(node.left!=null){
            maxB=Math.max(maxB,leftMax[1]);
        }
        if(node.right!=null){
            maxB=Math.max(maxB,rightMax[1]);
        }
        return new int[]{maxA,maxB};

    }
}
